package demo.practice.dfs;

import java.util.*;

public class P212 {

    public static void main(String[] args) {
        P212 p212 = new P212();
        p212.findWords(new char[][]{{'a', 'a'}}, new String[]{"aaa"});
    }

    public List<String> findWords(char[][] board, String[] words) {
        Trie t = new Trie();
        for (String word : words) {
            t.insert(word);
        }
        int h = board.length;
        int w = board[0].length;
        Set<String> res = new HashSet<>();

        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                dfs(res, t, i, j, board, visited);
            }
        }
        return new ArrayList<>(res);
    }

    public void dfs(Set<String> res, Trie t, int i, int j, char[][] board, boolean[][] visited) {
       /* if (t.word != null) {
            res.add(t.word);
        }*/

        if (visited[i][j])
            return;
        char c = board[i][j];
        if (!t.child.containsKey(c))
            return;

        Trie child = t.child.get(c);


        if (child.word != null) {
            res.add(child.word);
        }

        visited[i][j]=true;
        if (i + 1 < board.length) {
            dfs(res, child, i + 1, j, board, visited);
        }
        if (i - 1 >= 0) {
            dfs(res, child, i - 1, j, board, visited);
        }
        if (j - 1 >= 0) {
            dfs(res, child, i, j - 1, board, visited);
        }
        if (j + 1 < board[0].length) {
            dfs(res, child, i, j + 1, board, visited);
        }
        visited[i][j] = false;
    }

    class Trie {
        public Map<Character, Trie> child = new HashMap<>();
        //public boolean isend = false;
        public String word;

        public void insert(String word) {
            Trie cur = this;
            for (char c : word.toCharArray()) {
                if (!cur.child.containsKey(c)) {
                    cur.child.put(c, new Trie());
                }
                cur = cur.child.get(c);
            }
            //cur.isend = true;
            cur.word = word;
        }

    }
}
